package slidingwindow;

import com.sun.xml.internal.ws.policy.EffectiveAlternativeSelector;

import java.util.HashMap;
import java.util.Map;

public class solution567 {
    public static boolean checkInclusion(String s1, String s2) {
        /*记录一下滑动窗口中出现t中元素的次数*/
        Map<Character,Integer> windows = new HashMap<>();
        Map<Character,Integer> needs = new HashMap<>();

        int left = 0;
        int right = 0;
        /*valid记录windows中满足need条件的字符的个数，如果valid==need.size()，则说明window满足条件*/
        int valid = 0;

        /*
         * 统计一下t中出现了哪些字符，并且这些字符出现了几次
         * */
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            needs.put(c,needs.getOrDefault(c,0)+1);
        }

        /*
         * 开始写框架
         * */
        while(right < s2.length()){
            char c = s2.charAt(right);
            right++;

            //更新数据，我们先判断一下是否要把当前的字符放入windows中统计
            if(needs.containsKey(c)){
                windows.put(c,windows.getOrDefault(c,0)+1);
                if (windows.get(c).equals(needs.get(c))){
                    valid++;
                }
            }

            //while(window need shrink)
            //让左右指针之间距离保持right-left的长度
            while(right-left >= s1.length()){

                //判定条件
                if (valid == needs.size())
                    return true;

                char cRemove = s2.charAt(left);
                left++;

                //依旧更新数据
                if (needs.containsKey(cRemove)){
                    if (windows.get(cRemove).equals(needs.get(cRemove))){
                        valid--;
                    }
                    windows.put(cRemove,windows.get(cRemove)-1);
                }


            }
        }

        return false;


    }

    public static void main(String[] args) {
        boolean checked = checkInclusion("a", "ab");
        System.out.println("checked = " + checked);
    }
}
